package leetcode.problems;

import org.junit.Test;

import java.util.Arrays;

/**
 * Created by gmwang on 2018/7/25
 * 传统排序字符串
 */
public class _0826CustomSortString {
    /**
     *
     * S and T are strings composed of lowercase letters. In S, no letter occurs more than once.
     * S和T是由小写字母组成的字符串。在S中，每个字母出现仅出现一次。
     * S was sorted in some custom order previously. We want to permute the characters of T so that they match the order that S was sorted.
     * S按以前的自定义顺序排序。我们想要对T的字符进行置换，使它们与S排序的顺序相匹配。
     *
     * More specifically, if x occurs before y in S, then x should occur before y in the returned string.
     * 更具体地说，如果X在S中出现在Y之前，那么X应该出现在返回字符串中y之前。
     *
     * Return any permutation of T (as a string) that satisfies this property.
     * 返回满足这个属性的T（作为字符串）的任何置换。
     *
     * Example :
     * Input:
     * S = "cba"
     * T = "abcd"
     * Output: "cbad"
     * Explanation:
     * "a", "b", "c" appear in S, so the order of "a", "b", "c" should be "c", "b", and "a".
     * Since "d" does not appear in S, it can be at any position in T. "dcba", "cdba", "cbda" are also valid outputs.
     /**
     *
     * @param S,T
     * @return
     */
//    public String customSortString(String S, String T) {
//        StringBuilder builder = new StringBuilder();
//        String [] s = new String [T.length()];
//        char[] chars = T.toCharArray();
//        for (int i = 0; i < T.length(); i++) {
//            if(S.indexOf(chars[i]) == -1){
//                if(s[T.length() - 1] == null){
//                    s[T.length() - 1] = String.valueOf(chars[i]);
//                }else {
//                    s[T.length() - 1] = s[T.length() - 1]+","+String.valueOf(chars[i]);
//                }
//            }else{
//                if(s[S.indexOf(chars[i])] == null){
//                    s[S.indexOf(chars[i])] = String.valueOf(chars[i]);
//                }else {
//                    s[S.indexOf(chars[i])] = s[S.indexOf(chars[i])]+","+String.valueOf(chars[i]);
//                }
//
//            }
//        }
//        for (int i = 0; i < T.length(); i++) {
//            if(s[i] != null){
//                if(s[i].indexOf(",") != -1){
//                    String[] strings = s[i].split(",");
//                    for (int j = 0; j < strings.length; j++) {
//                        builder.append(strings[j]);
//                    }
//                }else {
//                    builder.append(s[i]);
//                }
//            }
//        }
//        return builder.toString();
//    }

    public String customSortString(String S, String T) {
        int[] num = new int[26];

        // count the number of 26 letters
        for (int i = 0; i < T.length(); i++)
            num[T.charAt(i) - 'a']++;

        // arr is to generate the target string
        char[] arr = new char[T.length()];
        int offset = 0;
        // whether a letter appears in string S
        boolean[] existing = new boolean[26];

        for (int i = 0; i < S.length(); i++) {
            existing[S.charAt(i) - 'a'] = true;
            // fill letters in the order of appearance in string S
            int count = num[S.charAt(i) - 'a'];
            Arrays.fill(arr, offset, offset + count, S.charAt(i));
            offset += count;
        }

        // fill the remaining letters in arbitrary order
        for (int i = 0; i < 26; i++)
            if (!existing[i]) {
                Arrays.fill(arr, offset, offset + num[i], (char)(i + 'a'));
                offset += num[i];
            }

        return String.valueOf(arr);
    }
    @Test
    public void test() {
//        String a = "cba";
//        String b =  "abcd";

//        String a = "kqep";   // "kqeep"
//        String b = "pekeq";

        String a = "disqyr";
        String b = "iwyrysqrdj";  //"disqyyrrjw"

//        String a = "horbxeemlgqpqbujbdagizcfairalg";
//        String b = "iwvtgyojrfhyzgyzeikqagpfjoaeen";  //30
        String res = customSortString(a,b);
        System.out.println(res);
    }
}
